// 图算法
import { values, groupBy } from 'lodash-es'

type INodeId = string

type INode = { code: INodeId; hideFlag: boolean }

type IEdge = { source: string; target: string }

function dfsRelation(edges: IEdge[], { source, target }: { source: INodeId; target: INodeId }) {
  let graph: Record<INodeId, INodeId[]> = {}
  for (let relation of edges) {
    let { source, target } = relation
    if (!graph[source]) {
      graph[source] = []
    }
    graph[source].push(target)
  }
  // 创建一个辅助函数来执行深度优先搜索
  function dfs(current: INodeId, target: INodeId, relation: Set<INodeId>) {
    if (current === target) {
      return true // 找到目标节点，返回 true
    }
    if (relation.has(current)) {
      return false // 避免进入循环，已访问过的节点直接返回 false
    }
    relation.add(current)
    if (graph[current]) {
      for (let neighbor of graph[current]) {
        if (dfs(neighbor, target, relation)) {
          return true // 在邻居节点中找到目标节点，返回 true
        }
      }
    }
    return false
  }
  // 调用深度优先搜索函数，判断两个 ID 是否有关系
  return dfs(source, target, new Set())
}

// 深度邮箱，拓补排序
export function dfsSort(nodeList: INode[], edgeList: IEdge[]) {
  const hideFlagIds: INodeId[] = []
  if (!nodeList) return { nodes: [], edges: [] }
  const nodes = nodeList.filter((e) => {
    const show = !e.hideFlag
    if (!show) hideFlagIds.push(e.code)
    return show
  })
  let edges = edgeList

  // 隐藏节点
  hideFlagIds.forEach((hideNodeId) => {
    const sourceNodeList: INodeId[] = []
    const targetList: INodeId[] = []
    edges = edges.filter(({ source, target }) => {
      // 移除相关线，并计算原前后节点
      if (source === hideNodeId) return !targetList.push(target)
      if (target === hideNodeId) return !sourceNodeList.push(source)
      return true
    })
    const [{ length: prevNum }, { length: nextNum }] = [sourceNodeList, targetList]
    if (prevNum >= 1 && nextNum >= 1) {
      for (let source of sourceNodeList)
        for (let target of targetList) {
          // 判断两个节点有没有链接关系
          if (!dfsRelation(edges, { source, target })) edges.push({ source, target })
        }
    }
  })

  const adjList: Record<INodeId, INodeId[]> = {}
  const incomingEdges: Record<INodeId, INodeId[]> = {} // 记录每个节点的入边
  const outgoingEdges: Record<INodeId, INodeId[]> = {} // 记录每个节点的出边

  for (const node of nodes) {
    adjList[node.code] = []
    incomingEdges[node.code] = []
    outgoingEdges[node.code] = []
  }

  for (const edge of edges) {
    adjList[edge.source].push(edge.target)
    incomingEdges[edge.target].push(edge.source)
    outgoingEdges[edge.source].push(edge.target)
  }

  const relation: Record<INodeId, INode & { id: INodeId; depth: number; sources: INodeId[]; targets: INodeId[] }> = {}
  const resultNodes = []

  function dfs(nodeId: INodeId, depth: number) {
    if (!relation[nodeId]) {
      const node = nodes.find((e) => e.code === nodeId) as INode
      relation[nodeId] = {
        id: nodeId,
        depth,
        ...node,
        sources: incomingEdges[nodeId],
        targets: outgoingEdges[nodeId],
      }
    } else {
      relation[nodeId].depth = Math.max(relation[nodeId].depth, depth)
    }
    // relation[nodeId] = true;
    // const node = nodes.find((e) => e.code === nodeId);
    // // 记录节点信息
    // resultNodes.push({
    //   id: nodeId,
    //   depth,
    //   ...node,
    //   sources: incomingEdges[nodeId],
    //   targets: outgoingEdges[nodeId],
    // });

    const neighbors = adjList[nodeId]

    for (const neighbor of neighbors) {
      // if (!relation[neighbor]) {
      dfs(neighbor, depth + 1)
      // }
    }
  }

  // 遍历所有节点，进行 DFS
  for (const node of nodes) {
    if (!relation[node.code]) {
      dfs(node.code, 0)
    }
  }

  for (const nodeId in relation) {
    resultNodes.push(relation[nodeId])
  }

  return { nodes: values(groupBy(resultNodes, 'depth')), edges }
}
